package com.snopy.datastructure.tree;

import lombok.extern.slf4j.Slf4j;

import java.util.*;

/**
 * @author snopy
 * @version 1.0.0
 * @classname Tree
 * @description
 * @email 77912204@qq.com
 * @date 2022/03/12 12:58
 */
@Slf4j
public class TreeNode {


    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1,new TreeNode(4),new TreeNode(2,new TreeNode(3),null));
        Solution solution = new Solution();
/*        List<Integer> integers = solution.preorderTraversal(root);

        for (Integer i:integers) {
            log.info("{}",i);
        }*/
        /*List<Integer> inOrderList = solution.inorderTraversal(root);
        for (Integer i:inOrderList) {
            log.info("{}",i);
        }*/
/*        List<Integer> postOrderList = solution.postOrderTraversal(root);
        for (Integer i:postOrderList) {
            log.info("{}",i);
        }*/
        List<List<Integer>> levelOrderList = solution.levelOrderTraversal(root);
        log.info(levelOrderList.toString());
    }
}
class Solution{



    public List<Integer> preorderTraversal(TreeNode root){
        List<Integer> list= new ArrayList<>();
        preOrder(root,list);
        return list;
    }
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> list= new ArrayList<>();
        inOrder(root,list);
        return list;
    }
    public List<Integer> postOrderTraversal(TreeNode root){
        List<Integer> list= new ArrayList<>();
        postOrder(root,list);
        return list;
    }

    public List<List<Integer>> levelOrderTraversal(TreeNode root){

        List<List<Integer>> list = new ArrayList<>();
        if (root==null){
            return null;
        }
        List<Integer> temp;
        Queue<TreeNode> stack = new LinkedList<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            temp = new ArrayList<>();
            int size = stack.size();
            for (int i =0;i<size;i++) {
                root = stack.poll();
                temp.add(root.val);
                if (root.right != null) {
                    stack.add(root.right);
                }
                if (root.left != null) {
                    stack.add(root.left);
                }
            }
            list.add(temp);
        }
        return list;
    }

    private void preOrder(TreeNode node,List<Integer> list){
        if (node==null)
            return;
            list.add(node.val);
            preOrder(node.left,list);
            preOrder(node.right,list);
    }
    private void inOrder(TreeNode node,List<Integer> list){
        if (node==null)
            return;
        inOrder(node.left,list);
        list.add(node.val);
        inOrder(node.right,list);
    }
    private void postOrder(TreeNode node,List<Integer> list){
        if (node==null)
            return;
        postOrder(node.left,list);
        postOrder(node.right,list);
        list.add(node.val);
    }
    private void levelOrder(TreeNode node,List<List<Integer>> list){
        if (node==null){
            return;
        }
    }

    /**
     * @Description
     * @param root:
     * @return: int
     * @Date 2022-03-13
     * @Author txl77912204@gmail.com
     **/
    public int maxDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        int depth = 1;

        return 0;
    }
    private void preOrderMaxDepth(TreeNode node,int depth){
        if (node==null)
            return;
        depth= depth+1;
        preOrderMaxDepth(node.left,depth);
        preOrderMaxDepth(node.right,depth);
    }
}